package com.cat.binaryTree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/all-possible-full-binary-trees/?envType=problem-list-v2&envId=xhsq2On3
 * @create 2025/10/2 20:22
 * @since JDK17
 */

public class Solution99 {
    static List<TreeNode>[] ans = new List[11];
    static {
        Arrays.setAll(ans, i -> new ArrayList<>());
        ans[1].add(new TreeNode(0));
        for (int i = 2; i < 11; i++) {
            for (int j = 1; j < i; j++) {
                for (var left : ans[j]) {
                    for (var right : ans[i - j]) {
                        ans[i].add(new TreeNode(0, left, right));
                    }
                }
            }
        }
    }

    public List<TreeNode> allPossibleFBT(int n) {
        return n % 2 == 0 ? new ArrayList<TreeNode>() : ans[(n + 1) / 2];
    }
}
